package d2;
import java.util.*;

public class Day7 {
    public static void main(String[] args) {
        Set<int[]> set = new HashSet<>();
        int[] tmp = {1,1};
        set.add(tmp);
        int[] t = {1,1};
        set.add(t);
        set.add(tmp);
        char[][] a = {{'+','+','+'},{'.','.','.'},{'+','+','+'}};
        int[] b = {1,0};
        //nearestExit(a,b);
        combinationSum3(3,7);
    }

    //组合总和Ⅲ
    static List<List<Integer>> ret = new ArrayList<>();
    static List<Integer> path = new ArrayList<>();
    static int n,k;
    public static List<List<Integer>> combinationSum3(int _k, int _n) {
        //k当前个数，n总和
        n=_n;k=_k;
        dfs(0,0,1);
        return ret;
    }
    public static void dfs(int index,int sum,int pos) {
        if(sum>=n || index==k) {
            if(sum>n || sum<n) return;
            ret.add(new ArrayList<>(path));
            return;
        }
        for(int i=pos;i<=9;i++) {
            path.add(i);
            dfs(index+1,sum+i,i+1);
            //回溯
            path.remove(path.size()-1);
        }
    }

    //bfs最短路径
    public int nearestExit(char[][] maze, int[] entrance) {
        int m=maze.length,n=maze[0].length;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{entrance[0],entrance[1]});
        int[] dx = {1,-1,0,0};
        int[] dy = {0,0,-1,1};
        int ret=0;
        boolean bool = false;
        boolean[][] ck = new boolean[m][n];
        while(!queue.isEmpty()) {
            int sz = queue.size();
            for(int i=sz;i>0;i--) {
                int[] t = queue.poll();
                int a = t[0],b = t[1];
                ck[a][b]=true;
                for(int k=0;k<4;k++) {
                    int x=a+dx[k],y=b+dy[k];
                    if(x>=0&&x<m&&y>=0&&y<n && maze[x][y]!='+' && !ck[x][y]) {
                        if(x==0||y==0||x==m-1||y==n-1) {//找到出口
                            bool=true;
                            ret++;
                            break;
                        }
                        queue.add(new int[]{x,y});
                        ck[x][y]=true;
                    }
                }
                if(bool) break;
            }
            if(bool) break;
            if(!queue.isEmpty()) ret++;
        }
        if(bool) return ret;
        return -1;
    }



    //被围绕的区域
    public void solve(char[][] board) {
        int[] dx = {1,-1,0,0};
        int[] dy = {0,0,1,-1};
        int m=board.length,n=board[0].length;
        boolean[][] ck = new boolean[m][n];
        //1.将所有的边缘O入队列
        Queue<int[]> queue = new LinkedList<>();
        for(int i=0;i<m;i++) {
            if(board[i][0]=='O') queue.add(new int[]{i,0});
            if(board[i][n-1]=='O') queue.add(new int[]{i,n-1});
        }
        for(int i=0;i<n;i++) {
            if(board[0][i]=='O') queue.add(new int[]{0,i});
            if(board[m-1][i]=='O') queue.add(new int[]{m-1,i});
        }
        //2.将所有边缘O都进行了标记
        while(!queue.isEmpty()) {
            int[] t = queue.poll();
            int a = t[0];
            int b = t[1];
            ck[a][b]=true;
            for(int k=0;k<4;k++) {
                int x = a + dx[k];
                int y = b + dy[k];
                if(x>=0&&x<m&&y>=0&&y<n && !ck[x][y] && board[x][y]=='O') {
                    ck[x][y]=true;
                    queue.add(new int[]{x,y});
                }
            }
        }
        //3.将没有被标记的O修改成X
        for(int i=1;i<m-1;i++)
            for(int j=1;j<n-1;j++) {
                if(board[i][j]=='O'&&!ck[i][j]) {
                    board[i][j]='X';
                    ck[i][j]=true;
                }
            }
        //
    }

}
